{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 试画图说明极线几何关系，并指出极点、极线所在，解释极线约束。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img style=\"float: center;\" src=\"./images/极线几何.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**极点：基础线与量摄像机图像平面的交点，分别为图中的$e_l$和$e_r$点；**<br>\n",
    "**极线：极平面与图像平面的交线，分别为图中$P_le_l$和$P_re_r$线段**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**极线几何关系：**\n",
    "<img style=\"float: center;\" src=\"./images/极线几何关系.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "图中$X_cY_cZ_c$为相机坐标系，$X_wY_wZ_w$为世界坐标系，$xO_ly$为图像坐标系<br>\n",
    "图像坐标系和相机坐标系的转换关系为：\n",
    "<img style=\"float: center;\" src=\"./images/极线几何关系2.png\" width=\"20%\">\n",
    "又由于同一点在二相机坐标系间关系满足旋转和平移关系，再代入上面图像坐标和相机坐标转换关系得到下图结果：\n",
    "<img style=\"float: center;\" src=\"./images/极线几何关系3.png\" width=\"40%\">\n",
    "通过叉积和点积的变换，最终将空间中任何一个点在两相机图像坐标系的成像通过3x3的本质矩阵关联起来。如下图结果：\n",
    "<img style=\"float: center;\" src=\"./images/极线几何关系4.png\" width=\"40%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 结合本质矩阵的定义，说明本质矩阵的意义，同时思考与上一周中平面点对应透视矩阵的区别。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**本质矩阵的意义是将空间中任何一个点在两相机坐标系下的成像通过一个3x3的矩阵完全关联起来**<br>\n",
    "通过多个空间点在两相机坐标系下的成像的对应关系，我们求出本质矩阵，然后从本质矩阵中求出对应的旋转和平移矩阵。通过拍摄相邻两帧多个点，我们可以得到相邻两帧位姿变换关系。这样我们通过求本质矩阵就能实现三维结构恢复。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**区别**：\n",
    "单应矩阵反应的是世界坐标系下平面上的点之间的对应关系，就是现实平面上的点到相机平面上的点的射影变换矩阵，具有8个自由度，就是说单应矩阵就是射影变换。相反，本质矩阵或基础矩阵则没有这个限制。而基础矩阵或本质矩阵反应的则是图像平面点x对应的真实点X在另一幅图像的投影点x’在对极线上的关系。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 说明三维重构的步骤，并指出输入及输出要求。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**三维重构步骤：**\n",
    "* 首先有两个相机，对物体拍两幅照片，提取图片中的特征点，然后建立特征匹配；\n",
    "* 计算匹配点之间的视差，然后进行线性差值和平滑等处理，为了得到比较好的重构效果，取深度信息变化比较大的特征点；\n",
    "* 计算每个特征点的世界坐标；\n",
    "* 为了恢复对象完整的三维结构，先要进行三角剖分；\n",
    "* 利用三角剖分的结果，通过openGL绘制，得到最终的三维重构结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 说明特征匹配的步骤，进一步说明基于k-d树的特征匹配方法的思路。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**特征匹配：**首先输入图像，对图像进行特征检测得到每个特征点的向量描述，通过匹配算法和滤波算法得到最终的识别结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**基于k-d树的特征匹配方法思路**\n",
    "\n",
    "**k-d树：**由于基于暴力搜索的方法的时间复杂度为$O(n^2)$,特征数量多时，匹配效率很低，通过二叉搜索树的方式，能够提高搜索效率，但是二叉树不能搜索高维特征点，因此产生基于k-d树的方法。k-d树对于每一层指定一个维度划分，然后依次进行，比如对于二维特征点，第一层对x维进行划分，第二层对y维进行划分，第三层再对x维进行划分，依次进行划分。流程如下图所示：\n",
    "<img style=\"float: center;\" src=\"./images/k-d树.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根节点为（53，14），第一层很明显基于x轴划分，左边的节点x坐标小于根节点，右边节点的x坐标大于根节点；第二层基于y轴划分，左孩子节点y轴坐标小于父节点，右孩子节点y轴坐标大于父节点；第三层又开始基于x坐标划分，依次进行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**k-d树建立方式：**对于所有样本点，计算它们在每一维度的方差，挑选出方差最大值，从该值对应的维开始进行划分，因为数据方差最大，表面在该维能够将数据分得最开，这个方向进行数据分割能够获得最好的分辨率。然后再将所有点按该维的值进行排序，位于正中间的那个点选为分裂节点对应域。重复上述过程，直至获得所有叶子节点。下图对应着上述划分过程的示例：\n",
    "假设样本集为{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}。\n",
    "<img style=\"float: center;\" src=\"./images/k-d树建立方式.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**k-d树最近邻查询算法：**<br>\n",
    "1、首先通过将查找点数据根结点数据对应维上的值相比较，按照二叉搜索的方式，顺着“搜索路径”找到最近邻的近似点，也就是与查询点处于同一个子空间的叶子节点;<br>\n",
    "2、为了防止漏查与查找点跟迕的距离的点，回溯搜索路径，并且判断搜索路径上节点的其他子节点空间中是否有距离查询点更近的数据点，如果有，则需要跳到其他子节点空间中去搜索。<br>\n",
    "3、重复这个过程直到搜索路径为空。<br>\n",
    "以下图为例：\n",
    "<img style=\"float: center;\" src=\"./images/k-d树查询.png\" width=\"50%\">\n",
    "<img style=\"float: center;\" src=\"./images/k-d树查询2.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设查询点为（2，4.5），首先通过x轴比较，(2,4.5)小于(7,2), 进入根结点的左子树，再进行y轴比较，(2,4.5)大于(5,4)，因此将(2,4.5)与(4,7)计算距离为3.2，再将(2,4.5)与(5,4)计算距离为3.0，此时以(5,4)在圆上，以(2,4.5)为圆心画圆，如上图所示，由于圆与划分平面有交点，继续以圆内的距离该点更近的(2,3)在圆上，(2,4.5)为圆心画圆，此时圆与根结点的分界平面没有交点，因此整个右子树不必再搜索，搜索结束，查询到的与(2,4.5)最近的点为(2,3)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**改进1:(BBF(Best Bin First))**<br>\n",
    "BBF的查询思路就是将“查询路径”上的节点进行排序，如按各自分割超平面(称为Bin)与查询点的距离排序,优先考虑距离小的点。BBF还设置了一个运行超时限制，当优先级队列中的所有节点都经过检查或者超出时间限制时，算法返回当前找到的最好结果作为近似的最近邻。<br>\n",
    "**改进2:(随机化k-d森林):**<br>\n",
    "同时独立建立多个k-d树，每棵树在具有大方差的各维中(如top-5)随机选择。查询时，并行查询多个k-d树，按照BBF准侧将候选节点放在同一队列中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. 说明RANSAC方法的基本思想及实施步骤。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**基本思想及实施步骤：**\n",
    "RANSAC是一种稳健估计方法，可有效消除误配点。其基本思想是通过随机反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证:<br>\n",
    "* 1. 有一个模型适应于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。\n",
    "* 2. 用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。\n",
    "* 3. 如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。\n",
    "* 4. 然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。\n",
    "* 5. 最后，通过估计局内点与模型的错误率来评估模型。\n",
    "这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用。<br>\n",
    "整个过程如下面示意图所示：\n",
    "<img style=\"float: center;\" src=\"./images/RANSAC.png\" width=\"80%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "首先图1随机选择了两个红点，然后图2根据这两个点拟合模型，图3计算每个点到这条拟合直线的误差，图4为选择符合假设的点，即两条虚线范围内的绿色点为假设的局内点，图5和图6为重复采样两个点重复上述过程直至产生拟合这些数据点的最佳模型。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
